Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link
11	Johan S. Wind, Vegard Antun, Anders C. Hansen	Implicit regularization in AI meets generalized hardness of approximation in optimization - Sharp results for diagonal linear networks.	CoRR	2023	DBLP DOI BibTeX RDF
11	Alex Fischer, Akimasa Miyake	Hardness results for decoding the surface code with Pauli noise.	CoRR	2023	DBLP DOI BibTeX RDF
11	Chae-Yeun Park, Pablo A. M. Casares, Juan Miguel Arrazola, Joonsuk Huh	The hardness of quantum spin dynamics.	CoRR	2023	DBLP DOI BibTeX RDF
11	Peter Bürgisser, Gorav Jindal	On the Hardness of PosSLP.	CoRR	2023	DBLP DOI BibTeX RDF
11	Feyza Duman Keles, Chinmay Hegde	On the Fine-Grained Hardness of Inverting Generative Models.	CoRR	2023	DBLP DOI BibTeX RDF
11	Yilei Chen 0001, Zihan Hu, Qipeng Liu 0001, Han Luo, Yaxin Tu	On the Hardness of S\|LWE〉 with Gaussian and Other Amplitudes.	CoRR	2023	DBLP DOI BibTeX RDF
11	Soumyashree Rana, Sounaka Mishra, Bhawani Sankar Panda	Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results.	CoRR	2023	DBLP DOI BibTeX RDF
11	Radu Curticapean	Count on CFI graphs for #P-hardness.	CoRR	2023	DBLP DOI BibTeX RDF
11	Xin Li 0006, Yan Zhong 0002	Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren	Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.	CoRR	2023	DBLP DOI BibTeX RDF
11	Alexander Bastounis, Felipe Cucker, Anders C. Hansen	When can you trust feature selection? - I: A condition-based analysis of LASSO and generalised hardness of approximation.	CoRR	2023	DBLP DOI BibTeX RDF
11	Ziqian Zeng, Yihuai Hong, Hongliang Dai, Huiping Zhuang, Cen Chen	ConsistentEE: A Consistent and Hardness-Guided Early Exiting Method for Accelerating Language Models Inference.	CoRR	2023	DBLP DOI BibTeX RDF
11	Diego Maldonado, Pedro Montealegre 0001, Martín Ríos Wilson	The Hardness of Local Certification of Finite-State Dynamics.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jian Ding, Hang Du, Zhangsong Li	Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Somnath Chakraborty 0001	On hardness of computing analytic Brouwer degree.	CoRR	2023	DBLP DOI BibTeX RDF
11	Kusum, Arti Pandey	Cosecure Domination: Hardness Results and Algorithm.	CoRR	2023	DBLP DOI BibTeX RDF
11	Hai Ye, Hwee Tou Ng, Wenjuan Han	On the Robustness of Question Rewriting Systems to Questions of Varying Hardness.	CoRR	2023	DBLP DOI BibTeX RDF
11	Ronen Shaltiel, Emanuele Viola	On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
11	Ming Shi, Yingbin Liang, Ness B. Shroff	Theoretical Hardness and Tractability of POMDPs in RL with Partial Hindsight State Information.	CoRR	2023	DBLP DOI BibTeX RDF
11	Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou	Public-key pseudoentanglement and the hardness of learning ground state entanglement structure.	CoRR	2023	DBLP DOI BibTeX RDF
11	Nick Fischer, Piotr Kaliciak, Adam Polak 0001	Deterministic 3SUM-Hardness.	CoRR	2023	DBLP DOI BibTeX RDF
11	Julian Müllner, Marcel Moosbrugger, Laura Kovács	Strong Invariants Are Hard: On the Hardness of Strongest Polynomial Invariants for (Probabilistic) Programs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Suprovat Ghoshal, Euiwoong Lee	On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Kunihiro Wasa, Shin Nishio, Koki Suetsugu, Michael Hanks, Ashley Stephens, Yu Yokoi, Kae Nemoto	Hardness of braided quantum circuit optimization in the surface code.	CoRR	2023	DBLP DOI BibTeX RDF
11	Dylan J. Foster, Noah Golowich, Sham M. Kakade	Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jingyang Zhao 0001, Mingyu Xiao 0001	The APX-hardness of the Traveling Tournament Problem.	CoRR	2023	DBLP DOI BibTeX RDF
11	Maxime Bombar, Geoffroy Couteau, Alain Couvreur, Clément Ducros	Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding.	CoRR	2023	DBLP DOI BibTeX RDF
11	Dhanyamol Antony, L. Sunil Chandran, Ankit Gayen, Shirish Gosavi, Dalu Jacob	Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness.	CoRR	2023	DBLP DOI BibTeX RDF
11	Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto	Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.	CoRR	2023	DBLP DOI BibTeX RDF
11	M. A. Shalu, Cyriac Antony	Hardness Transitions of Star Colouring and Restricted Star Colouring.	CoRR	2023	DBLP DOI BibTeX RDF
11	Xiong Zeng, Zexiang Liu, Zhe Du, Necmiye Ozay, Mario Sznaier	On the Hardness of Learning to Stabilize Linear Systems.	CoRR	2023	DBLP DOI BibTeX RDF
11	Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals	Hardness of Approximation in PSPACE and Separation Results for Pebble Games.	CoRR	2023	DBLP DOI BibTeX RDF
11	Benito van der Zander, Markus Bläser, Maciej Liskiewicz	The Hardness of Reasoning about Probabilities and Causality.	CoRR	2023	DBLP DOI BibTeX RDF
11	Arnaud Casteigts, Timothée Corsini	In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Katharina Kreuzer, Tobias Nipkow	Verification of NP-hardness Reduction Functions for Exact Lattice Problems.	CoRR	2023	DBLP DOI BibTeX RDF
11	Ali Çivril	Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation.	CoRR	2023	DBLP DOI BibTeX RDF
11	Antoine Dailly, Florent Foucaud, Anni Hakanen	Algorithms and hardness for Metric Dimension on digraphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Daniel Kane 0001, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz	Exponential Hardness of Reinforcement Learning with Linear Function Approximation.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind S. Sankar, Philipp Schepper, Philip Wellnitz	Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results.	CoRR	2023	DBLP DOI BibTeX RDF
11	Tuukka Korhonen, Daniel Lokshtanov	Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jianyu Xu, Hanwen Zhang, Ling Liang, Lei Deng 0003, Yuan Xie 0001, Guoqi Li	NP-Hardness of Tensor Network Contraction Ordering.	CoRR	2023	DBLP DOI BibTeX RDF
11	Markus Hecher	Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?	CoRR	2023	DBLP DOI BibTeX RDF
11	Junyan Su, Qiulin Lin, Minghua Chen 0001, Haibo Zeng 0001	Minimizing Carbon Footprint for Timely E-Truck Transportation: Hardness and Approximation Algorithm.	CoRR	2023	DBLP DOI BibTeX RDF
11	Martin Avanzini, Georg Moser, Romain Péchoux, Simon Perdrix	On the Hardness of Analyzing Quantum Programs Quantitatively.	CoRR	2023	DBLP DOI BibTeX RDF
11	Gergely Csáji, David F. Manlove, Iain McBride, James Trimble 0001	Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jingfeng Wu, Wennan Zhu, Peter Kairouz, Vladimir Braverman	Private Federated Frequency Estimation: Adapting to the Hardness of the Instance.	CoRR	2023	DBLP DOI BibTeX RDF
11	Euiwoong Lee, Pasin Manurangsi	Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jakob Piribauer, Christel Baier	Positivity-hardness results on Markov decision processes.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jan van den Brand, Zhao Song 0002, Tianyi Zhou 0002	Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models.	CoRR	2023	DBLP DOI BibTeX RDF
11	Arka Ray, Sai Sandeep	Improved Hardness of Approximation for Geometric Bin Packing.	CoRR	2023	DBLP DOI BibTeX RDF
11	Anupam Gupta 0001, Amit Kumar 0001, Debmalya Panigrahi	Efficient Algorithms and Hardness Results for the Weighted k-Server Problem.	CoRR	2023	DBLP DOI BibTeX RDF
11	Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang	Improved Hardness of Approximating k-Clique under ETH.	CoRR	2023	DBLP DOI BibTeX RDF
11	Lai Tian, Anthony Man-Cho So	Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
11		HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baseline.	CoRR	2023	DBLP DOI BibTeX RDF
11	Yuyang Deng, Nidham Gazagnadou, Junyuan Hong, Mehrdad Mahdavi, Lingjuan Lyu	On the Hardness of Robustness Transfer: A Perspective from Rademacher Complexity over Symmetric Difference Hypothesis Space.	CoRR	2023	DBLP DOI BibTeX RDF
11	Xin Xiao, Daiguo Zhou, Jiagao Hu, Yi Hu, Yongchao Xu	Not All Pixels Are Equal: Learning Pixel Hardness for Semantic Segmentation.	CoRR	2023	DBLP DOI BibTeX RDF
11	Nicos Isaak, Loizos Michael	Experience and Prediction: A Metric of Hardness for a Novel Litmus Test.	CoRR	2023	DBLP DOI BibTeX RDF
11	Sagnik Saha, Nikolaj I. Schwartzbach, Prashant Nalini Vasudevan	The Planted k-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography.	CoRR	2023	DBLP DOI BibTeX RDF
11	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jie Xie, Mingying Zhu, Kai Hu 0005, Jinglan Zhang	Instance hardness and multivariate Gaussian distribution-based oversampling technique for imbalance classification.	Pattern Anal. Appl.	2023	DBLP DOI BibTeX RDF
11	John Haslegrave	Monitoring edge-geodetic sets: Hardness and graph products.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
11	B. S. Panda 0001, Pooja Goyal	Hardness results of global roman domination in graphs.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
11	Sharareh Alipour, Salman Parsa	Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles.	Discret. Math. Algorithms Appl.	2023	DBLP DOI BibTeX RDF
11	Bahar Taskesen, Soroosh Shafieezadeh-Abadeh, Daniel Kuhn 0001	Semi-discrete optimal transport: hardness, regularization and numerical solution.	Math. Program.	2023	DBLP DOI BibTeX RDF
11	Manne Kaushik, Abid Musa Mulla, Nikhil P. Raut	Effect of submerged arc welding process on hardness and impact properties of fabricated SAE 1020 low carbon steel plates.	Int. J. Manuf. Technol. Manag.	2023	DBLP DOI BibTeX RDF
11	Yanyi Liu, Rafael Pass	Toward Basing Cryptography on the Hardness of EXP.	Commun. ACM	2023	DBLP DOI BibTeX RDF
11	Youssef Amin, Christian Gianoglio, Maurizio Valle	Embedded real-time objects' hardness classification for robotic grippers.	Future Gener. Comput. Syst.	2023	DBLP DOI BibTeX RDF
11	Zhengzheng Sun, Lianfang Tian, Qiliang Du, Jameel Ahmed Bhutto	Sample hardness guided softmax loss for face recognition.	Appl. Intell.	2023	DBLP DOI BibTeX RDF
11	Andre Esser 0001, Javier A. Verbel, Floyd Zweydinger, Emanuele Bellini 0002	ttCryptographicEstimators: a Software Library for Cryptographic Hardness Estimation.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Leonid Reyzin	Proofs of Space with Maximal Hardness.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Karim Eldefrawy, Nicholas Genise, Nathan Manohar	On the Hardness of Scheme-Switching Between SIMD FHE Schemes.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Sagnik Saha, Nikolaj Ignatieff Schwartzbach, Prashant Nalini Vasudevan	The Planted k-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Benny Applebaum, Oded Nir	Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Charanjit S. Jutla, Chengyu Lin 0001	Ring-LWE Hardness Based on Ideals of Hidden Orders of Number Fields.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Yilei Chen 0001, Zihan Hu, Qipeng Liu 0001, Han Luo, Yaxin Tu	On the Hardness of $\sf{S\|LWE\rangle}$ with Gaussian and Other Amplitudes.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Maxime Bombar, Geoffroy Couteau, Alain Couvreur, Clément Ducros	Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Fernando Virdia	Popping "R-propping": breaking hardness assumptions for matrix groups over F_{2^8}.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Yizhi Huang, Rahul Ilango, Hanlin Ren	NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Yilei Chen, Jiatu Li	Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai	Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Zhedong Wang, Qiqi Lai, Feng-Hao Liu	Ring/Module Learning with Errors under Linear Leakage - Hardness and Applications.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Shun Watanabe, Kenji Yasunaga	Bit-Security Preserving Hardness Amplification.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
11	Jonatan D. Polanco, Carlos A. Jacanamejoy-Jamioy, Claudia L. Mambuscay, Jeferson F. Piamba, Manuel Guillermo Forero	Automatic Method for Vickers Hardness Estimation by Image Processing.	J. Imaging	2023	DBLP DOI BibTeX RDF
11	Yong Ling, Junyan Ni, Joachim Antonissen, Haithem Ben Hamouda, John Vande Voorde, Magd Abdel Wahab	Numerical prediction of microstructure and hardness for low carbon steel wire Arc additive manufacturing components.	Simul. Model. Pract. Theory	2023	DBLP DOI BibTeX RDF
11	Debasis Dwibedy, Rakesh Mohanty	A note on Hardness of Multiprocessor Scheduling with Scheduling solution Space Tree.	Comput. Sci.	2023	DBLP DOI BibTeX RDF
11	Zhixiang Xing, Xianxian Wang, Mengshuai Ning, Cunfu He, Xiucheng Liu	Micromagnetic and Robust Evaluation of Surface Hardness in Cr12MoV Steel Considering Repeatability of the Instrument.	Sensors	2023	DBLP DOI BibTeX RDF
11	Katharina Kreuzer	Hardness of Lattice Problems.	Arch. Formal Proofs	2023	DBLP BibTeX RDF
11	Senlin Fang, Zhengkun Yi, Tingting Mi, Zhenning Zhou, Chaoxiang Ye, Wanfeng Shang, Tiantian Xu 0001, Xinyu Wu 0001	TactONet: Tactile Ordinal Network Based on Unimodal Probability for Object Hardness Classification.	IEEE Trans Autom. Sci. Eng.	2023	DBLP DOI BibTeX RDF
11	Angelos Chatzimparmpas, Fernando Vieira Paulovich, Andreas Kerren	HardVis: Visual Analytics to Handle Instance Hardness Using Undersampling and Oversampling Techniques.	Comput. Graph. Forum	2023	DBLP DOI BibTeX RDF
11	Naghmeh Zamani, Heather Culbertson	Effects of Physical Hardness on the Perception of Rendered Stiffness in an Encountered-Type Haptic Display.	IEEE Trans. Haptics	2023	DBLP DOI BibTeX RDF
11	Sudhin Chandran, R. Rajesh, M. Dev Anand	Laser Beam Welded Aluminum-Titanium Dissimilar Sheet Metals: Neural Network Based Strength and Hardness Prediction Model.	Comput. J.	2023	DBLP DOI BibTeX RDF
11	Hideyuki Fujii, Yukio Takahashi, Jiei Hodohara, Norikazu Suzuki, Yuki Yamada, Yasuhiro Imabeppu, Naruhiro Irino	Estimation of Hardness and Residual Stress on End-Milled Surfaces Using Linear Regression Model.	Int. J. Autom. Technol.	2023	DBLP DOI BibTeX RDF
11	Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar	Envy-freeness and relaxed stability: hardness and approximation algorithms.	J. Comb. Optim.	2023	DBLP DOI BibTeX RDF
11	Sevag Gharibian, François Le Gall	Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.	SIAM J. Comput.	2023	DBLP DOI BibTeX RDF
11	Fabian Hinder, Valerie Vaquet, Johannes Brinkrolf, Barbara Hammer	On the Hardness and Necessity of Supervised Concept Drift Detection.	ICPRAM	2023	DBLP DOI BibTeX RDF
11	Daniele Rizzieri, Sarah Azimi, Luca Sterpone, Corrado De Sio, Thomas Borel, Viyas Gupta, Margherita Cardi	Programmable SEL Test Monitoring System for Radiation Hardness Assurance.	DSN-S	2023	DBLP DOI BibTeX RDF
11	Karim Eldefrawy, Nicholas Genise, Nathan Manohar	On the Hardness of Scheme-Switching Between SIMD FHE Schemes.	PQCrypto	2023	DBLP DOI BibTeX RDF
11	Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson 0007, John Wright	Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality.	SODA	2023	DBLP DOI BibTeX RDF